Task management often involves dividing a large task that is to be performed by a computer system into smaller tasks, and then scheduling execution of those smaller tasks. Traditional task management systems often turn each task into a “message”, and then use a message queue to hold the messages until the processing resources become available. When processing resources become available, the task represented by the message that is currently at the head of the message queue is performed.
Jobs take time to complete. How much time any given job instance takes to complete is affected by many factors, including the type and number of tasks required by the job, the type of resources required by those tasks, the quantity of those resources that exist in the system, and the current demands placed on those resources by other job instances. For example, a job type X may normally execute much faster than a job type Y, but a job type X that is executed by a system with fewer resources, or during a period where there is high contention for the resources, may execute slower than a job type Y in a more powerful or less busy system.
It is a common requirement to be able to predict when jobs are going to finish. Thus, it is common for systems to provide a “status bar” that is repeatedly updated to show the approximate ratio between the portion of a job that has been completed and the portion of the job that is not completed. In more sophisticated systems, such status bars may be supplemented with or replaced by predictions of how much time remains before a task is completed.
Unfortunately, such predictions are not always very accurate. In particular, it is difficult to generate accurate predictions before all tasks required by a job instance have even been created. Specifically, until all tasks required by a job instance have been created, the number of “currently-pending” tasks for the job instance does not accurately reflect the remaining work of the job instance. In a system in which any given task can create any number of child tasks, which themselves can create any number of child tasks, the accurate prediction of time remaining until job completion is particularly difficult.
Historical information may be used to predict the amount of time that remains in a pending job instance. For example, if job type X took an average of 20 minutes to complete the last time several times job type X was performed, and a particular instance of job type X was started 10 minutes ago, it can be predicted that the particular instance of job type X will finish in 10 minutes. Unfortunately, predicting time remaining for a particular instance of a job type based on past executions of the job type does not take into account the current state of the system. If the current state of the system is significantly different than the state of the system during the prior executions, any predictions based on those prior executions may be way off. In addition, predictions based on prior executions only work if there exists statistics for a representative sample of prior executions. The first time an instance of a particular job type is executed, no such statistics exist. Therefore, no prediction based on such statistics is possible.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.